home *** CD-ROM | disk | FTP | other *** search
/ Aminet 28 / Aminet 28 (1998)(GTI - Schatztruhe)[!][Dec 1998].iso / Aminet / dev / misc / vahunz.lha / vahunz / source / ubiqx / ubi_AVLtree.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-09-17  |  5.5 KB  |  304 lines
  1. /*
  2.  * This source file is part of Vahunz,
  3.  * a tool to make source code un-/more legible.
  4.  *
  5.  *--------------------------------------------------------------------------
  6.  *
  7.  * Vahunz and the Ugly library are Copyright (C) 1998 by
  8.  * Thomas Aglassinger <agi@giga.or.at>
  9.  *
  10.  * All rights reserved.
  11.  *
  12.  * Refer to the manual for more information.
  13.  *
  14.  *--------------------------------------------------------------------------
  15.  *
  16.  * Ubiqx library is Copyright (C) 1991-1998 by
  17.  * Christopher R. Hertel <crh@ubiqx.mn.org>
  18.  *
  19.  * Ubiqx library is free software; you can redistribute it and/or
  20.  * modify it under the terms of the GNU Library General Public
  21.  * License as published by the Free Software Foundation; either
  22.  * version 2 of the License, or (at your option) any later version.
  23.  *
  24.  */
  25. #include "ubi_AVLtree.h" 
  26. #include <stdlib.h> 
  27. static char b9F[] = "ubi_AVLtree\n\
  28. \t$Revision: 2.5 $\n\
  29. \t$Date: 1997/12/23 04:00:42 $\n\
  30. \t$Author: crh $\n";
  31. static e6M L1( e6M p )
  32. {
  33. e6M j3J;
  34. j3J = p->e2Q[w6O];
  35. p->e2Q[w6O] = j3J->e2Q[e4E];
  36. j3J->e2Q[e4E] = p;
  37. j3J->e2Q[i0E] = p->e2Q[i0E];
  38. j3J->h1V = p->h1V;
  39. if(j3J->e2Q[i0E])
  40. (j3J->e2Q[i0E])->e2Q[(int)(j3J->h1V)] = j3J;
  41. p->e2Q[i0E] = j3J;
  42. p->h1V = e4E;
  43. if( p->e2Q[w6O] )
  44. {
  45. p->e2Q[w6O]->e2Q[i0E] = p;
  46. (p->e2Q[w6O])->h1V = w6O;
  47. }
  48. p->n7P -= q2Q( j3J->n7P );
  49. (j3J->n7P)--;
  50. return( j3J );
  51. } 
  52. static e6M R1( e6M p )
  53. {
  54. e6M j3J;
  55. j3J = p->e2Q[e4E];
  56. p->e2Q[e4E] = j3J->e2Q[w6O];
  57. j3J->e2Q[w6O] = p;
  58. j3J->e2Q[i0E] = p->e2Q[i0E];
  59. j3J->h1V = p->h1V;
  60. if(j3J->e2Q[i0E])
  61. (j3J->e2Q[i0E])->e2Q[(int)(j3J->h1V)] = j3J;
  62. p->e2Q[i0E] = j3J;
  63. p->h1V = w6O;
  64. if(p->e2Q[e4E])
  65. {
  66. p->e2Q[e4E]->e2Q[i0E] = p;
  67. p->e2Q[e4E]->h1V = e4E;
  68. }
  69. p->n7P -= q2Q( j3J->n7P );
  70. (j3J->n7P)++;
  71. return( j3J );
  72. } 
  73. static e6M L2( e6M j5L )
  74. {
  75. e6M j3J, l1B;
  76. j3J = j5L->e2Q[w6O];
  77. l1B = j3J->e2Q[e4E];
  78. j3J->e2Q[e4E] = l1B->e2Q[w6O];
  79. l1B->e2Q[w6O] = j3J;
  80. j5L->e2Q[w6O] = l1B->e2Q[e4E];
  81. l1B->e2Q[e4E] = j5L;
  82. l1B->e2Q[i0E] = j5L->e2Q[i0E];
  83. l1B->h1V = j5L->h1V;
  84. j5L->e2Q[i0E] = l1B;
  85. j5L->h1V = e4E;
  86. j3J->e2Q[i0E] = l1B;
  87. j3J->h1V = w6O;
  88. if( j5L->e2Q[w6O] )
  89. {
  90. j5L->e2Q[w6O]->e2Q[i0E] = j5L;
  91. j5L->e2Q[w6O]->h1V = w6O;
  92. }
  93. if( j3J->e2Q[e4E] )
  94. {
  95. j3J->e2Q[e4E]->e2Q[i0E] = j3J;
  96. j3J->e2Q[e4E]->h1V = e4E;
  97. }
  98. if(l1B->e2Q[i0E])
  99. l1B->e2Q[i0E]->e2Q[(int)(l1B->h1V)] = l1B;
  100. switch( l1B->n7P )
  101. {
  102. case e4E :
  103. j5L->n7P = g8I; j3J->n7P = w6O; break;
  104. case g8I:
  105. j5L->n7P = g8I; j3J->n7P = g8I; break;
  106. case w6O:
  107. j5L->n7P = e4E; j3J->n7P = g8I; break;
  108. }
  109. l1B->n7P = g8I;
  110. return( l1B );
  111. } 
  112. static e6M R2( e6M j5L )
  113. {
  114. e6M j3J, l1B;
  115. j3J = j5L->e2Q[e4E];
  116. l1B = j3J->e2Q[w6O];
  117. j3J->e2Q[w6O] = l1B->e2Q[e4E];
  118. l1B->e2Q[e4E] = j3J;
  119. j5L->e2Q[e4E] = l1B->e2Q[w6O];
  120. l1B->e2Q[w6O] = j5L;
  121. l1B->e2Q[i0E] = j5L->e2Q[i0E];
  122. l1B->h1V = j5L->h1V;
  123. j5L->e2Q[i0E] = l1B;
  124. j5L->h1V = w6O;
  125. j3J->e2Q[i0E] = l1B;
  126. j3J->h1V = e4E;
  127. if( j5L->e2Q[e4E] )
  128. {
  129. j5L->e2Q[e4E]->e2Q[i0E] = j5L;
  130. j5L->e2Q[e4E]->h1V = e4E;
  131. }
  132. if( j3J->e2Q[w6O] )
  133. {
  134. j3J->e2Q[w6O]->e2Q[i0E] = j3J;
  135. j3J->e2Q[w6O]->h1V = w6O;
  136. }
  137. if(l1B->e2Q[i0E])
  138. l1B->e2Q[i0E]->e2Q[(int)(l1B->h1V)] = l1B;
  139. switch( l1B->n7P )
  140. {
  141. case e4E :
  142. j5L->n7P = w6O; j3J->n7P = g8I; break;
  143. case g8I :
  144. j5L->n7P = g8I; j3J->n7P = g8I; break;
  145. case w6O :
  146. j5L->n7P = g8I; j3J->n7P = e4E; break;
  147. }
  148. l1B->n7P = g8I;
  149. return( l1B );
  150. } 
  151. static e6M t9D( e6M p, char l3J )
  152. {
  153. if( p->n7P != l3J )
  154. p->n7P += q2Q(l3J);
  155. else
  156. {
  157. char r5P; 
  158. r5P = p->e2Q[(int)l3J]->n7P;
  159. if( ( g8I == r5P ) || ( p->n7P == r5P ) )
  160. p = ( (e4E==l3J) ? R1(p) : L1(p) ); 
  161. else
  162. p = ( (e4E==l3J) ? R2(p) : L2(p) ); 
  163. }
  164. return( p );
  165. } 
  166. static e6M s0W( e6M g2I,
  167. e6M l9D,
  168. char l3J )
  169. {
  170. while( l9D )
  171. {
  172. l9D = t9D( l9D, l3J );
  173. if( i0E == l9D->h1V )
  174. return( l9D );
  175. if( g8I == l9D->n7P )
  176. return( g2I );
  177. l3J = l9D->h1V;
  178. l9D = l9D->e2Q[i0E];
  179. }
  180. return( g2I );
  181. } 
  182. static e6M h1T( e6M g2I,
  183. e6M l9D,
  184. char l3J )
  185. {
  186. while( l9D )
  187. {
  188. l9D = t9D( l9D, h3H(l3J) );
  189. if( i0E == l9D->h1V )
  190. return( l9D );
  191. if( g8I != l9D->n7P )
  192. return( g2I );
  193. l3J = l9D->h1V;
  194. l9D = l9D->e2Q[i0E];
  195. }
  196. return( g2I );
  197. } 
  198. static void b5P( e6M *u8S,
  199. e6M k2O,
  200. e6M t1D )
  201. {
  202. register int i;
  203. register int o0E = sizeof( v5T );
  204. for( i = 0; i < o0E; i++ )
  205. ((unsigned char *)t1D)[i] = ((unsigned char *)k2O)[i];
  206. (*u8S) = t1D;
  207. if(k2O->e2Q[e4E ] )
  208. (k2O->e2Q[e4E ])->e2Q[i0E] = t1D;
  209. if(k2O->e2Q[w6O] )
  210. (k2O->e2Q[w6O])->e2Q[i0E] = t1D;
  211. } 
  212. static void t3R( g8Sh v5F,
  213. e6M e8Uh,
  214. e6M c2U )
  215. {
  216. e6M *Parent;
  217. v5T p7D;
  218. e6M c0W = &p7D;
  219. if( e8Uh->e2Q[i0E] )
  220. Parent = &((e8Uh->e2Q[i0E])->e2Q[(int)(e8Uh->h1V)]);
  221. else
  222. Parent = (e6M *)&(v5F->k4S);
  223. b5P( Parent, e8Uh, c0W );
  224. if( c2U->e2Q[i0E] )
  225. Parent = &((c2U->e2Q[i0E])->e2Q[(int)(c2U->h1V)]);
  226. else
  227. Parent = (e6M *)&(v5F->k4S);
  228. b5P( Parent, c2U, e8Uh );
  229. if( c0W->e2Q[i0E] )
  230. Parent = &((c0W->e2Q[i0E])->e2Q[(int)(c0W->h1V)]);
  231. else
  232. Parent = (e6M *)&(v5F->k4S);
  233. b5P( Parent, c0W, c2U );
  234. } 
  235. e6M j3V( e6M l9P )
  236. {
  237. (void)y6S( (y8Ut)l9P );
  238. l9P->n7P = g8I;
  239. return( l9P );
  240. } 
  241. h3R m0C( g8Sh v5F,
  242. e6M i8C,
  243. y8Or x1B,
  244. e6M *j9B )
  245. {
  246. e6M y0U;
  247. if( !(j9B) ) j9B = &y0U;
  248. if( n5F( v5F,
  249. (y8Ut)i8C,
  250. x1B,
  251. (y8Ut *)j9B ) )
  252. {
  253. if( (*j9B) )
  254. i8C->n7P = (*j9B)->n7P;
  255. else
  256. {
  257. i8C->n7P = g8I;
  258. v5F->k4S = (y8Ut)s0W( (e6M)v5F->k4S,
  259. i8C->e2Q[i0E],
  260. i8C->h1V );
  261. }
  262. return( z1Zy );
  263. }
  264. return( d5B ); 
  265. } 
  266. e6M c6W( g8Sh v5F,
  267. e6M g4C )
  268. {
  269. y8Ut p,
  270. *r3Vg;
  271. if( (g4C->e2Q[e4E]) && (g4C->e2Q[w6O]) )
  272. t3R( v5F, g4C, l9B( g4C ) );
  273. if( g4C->e2Q[i0E] )
  274. r3Vg = (y8Ut *)
  275. &((g4C->e2Q[i0E])->e2Q[(int)(g4C->h1V)]);
  276. else
  277. r3Vg = &( v5F->k4S );
  278. if( g8I == g4C->n7P )
  279. (*r3Vg) = NULL;
  280. else
  281. {
  282. p = (y8Ut)(g4C->e2Q[(int)(g4C->n7P)]);
  283. p->e2Q[i0E] = (y8Ut)g4C->e2Q[i0E];
  284. p->h1V = g4C->h1V;
  285. (*r3Vg) = p;
  286. }
  287. v5F->k4S = (y8Ut)h1T( (e6M)v5F->k4S,
  288. g4C->e2Q[i0E],
  289. g4C->h1V );
  290. (v5F->count)--;
  291. return( g4C );
  292. } 
  293. int z7Zy( int u0Qh, char *list[] )
  294. {
  295. if( u0Qh > 0 )
  296. {
  297. list[0] = b9F;
  298. if( u0Qh > 1 )
  299. return( 1 + r7F( --u0Qh, &(list[1]) ) );
  300. return( 1 );
  301. }
  302. return( 0 );
  303. } 
  304.